#include <stdio.h>
#include <stdlib.h>
#define maxsize 100
typedef union data {
    int num;
    char opera;
};
typedef struct tree
{
    data node;
    int tag;
    struct tree *left;
    struct tree *right;
};
//运算符号处理
int sign(char s)
{
    switch (s)
    {
    case '+':
        return 1;
        break;
    case '-':
        return 1;
        break;
    case '*':
        return 2;
        break;
    case '/':
        return 2;
        break;
    default:
        return -1;
    }
}
tree *creat_node(char c)
{
    tree *node = (tree *)malloc(sizeof(tree));
    if (c >= '0' && c <= '9')
    {
        int n = c - '0';
        node->node.num = n;
        node->tag = 0;
        node->left = node->right = NULL;
    }
    else
    {
        char ch = c;
        node->node.num = ch;
        node->tag = 1;
        node->left = node->right = NULL;
    }
    return node;
}
tree *transform(char *operation)
{
    tree *stack_1[maxsize], *stack_2[maxsize]; //s_1[]放已经构建成功的树
    int s1, s2;
    s1 = s2 = -1;
    while (*operation)
    {
        if (*operation >= '0' && *operation <= '9')
        {
            if (s1 == -1 && s2 != -1)
            {
                tree *node = NULL;
                stack_1[++s1] = node;
            }
            tree *node = creat_node(*operation);
            stack_1[++s1] = node;
        }
        else if (*operation == '+' || *operation == '-' || *operation == '*' || *operation == '/')
        {
            if (s2 == -1) //空栈
            {
                tree *node = creat_node(*operation);
                stack_2[++s2] = node;
            }
            else
            {
                tree *p;
                p = stack_2[s2];
                if (sign(*operation) > sign(p->node.opera)) //当前运算符优先级大于栈顶
                {
                    tree *node = creat_node(*operation);
                    stack_2[++s2] = node;
                }
                else
                {
                    stack_1[++s1] = stack_2[s2--];
                    tree *p = stack_1[s1--];
                    tree *l, *r;
                    r = stack_1[s1--];
                    l = stack_1[s1--];
                    p->left = l;
                    p->right = r;
                    stack_1[++s1] = p;
                    continue;
                }
            }
        }
        else if (*operation == '(')
        {
            //传入()内的表达式;
            char op[maxsize] = {0};
            int i = 1;
            ++operation;
            int count = 1; //'(' ++ ')'--
            while (count > 0)
            {
                if (*operation == '(')
                    count++;
                else if (*operation == ')')
                    count--;
                op[i++] = *operation;
                operation++;
            }
            op[0] = '#';
            op[i - 1] = '#';
            operation--; //回退一个地址单位
            stack_1[++s1] = transform(op);
        }
        else if (*operation == '#')
        {
            while (s2 >= 0)
            {
                stack_1[++s1] = stack_2[s2--];
                tree *p = stack_1[s1--];
                tree *l, *r;
                r = stack_1[s1--];
                l = stack_1[s1--];
                p->left = l;
                p->right = r;
                stack_1[++s1] = p;
            }
        }
        operation++;
    }
    return stack_1[s1];
}
void visit(tree *root)
{
    if (!root)
        return;
    visit(root->left);
    visit(root->right);
    if (root->tag == 0)
        printf("%3d", root->node.num);
    else if (root->tag == 1)
        printf("%3c", root->node.opera);
}
void transform_mid(tree *root)
{
    if (!root)
        return;

    if (!root->left && !root->right)
        printf("%d", root->node.num);
    else
    {
        printf("(");
        transform_mid(root->left);
        if (root->tag == 0)
            printf("%d", root->node.num);
        else if (root->tag == 1)
            printf("%c", root->node.opera);
        transform_mid(root->right);
        printf(")");
    }
}
int main()
{
    /*******************code*******************/
    char *opera = "#(1+2)*(-4)/(5-6)#";
    tree *root = transform(opera);
    visit(root);
    printf("\n");
    transform_mid(root);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}